package Offer.math;

import org.junit.Test;

/*
    题目: 数值的整数次方
         实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。
         不得使用库函数，同时不需要考虑大数问题。

    思路:
        按照常规的思路：利用while循环一层一层去计算;所以它的时间复杂度就是O(n),当n很大的时候就会超时！
        可以用快速幂来降低时间复杂度：（包括 迭代|递归）

    注:
        n=-2147483648是int的最小值了，如果直接取n=-n,得到的还是-2147483648

* */
public class T16_myPow {
    @Test
    public void test() {
//        System.out.println(myPow(2.00000, -2147483648));
        System.out.println(myPow(2.00000, 10));
    }

//    快速幂之迭代(二分的思想 时间复杂度为O(log2n ))
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }

        double res = 1;
        long m = n;     //防止n为-2147483648时取反溢出
        if (m < 0) {    //如果指数为负数
            m = -m;
            x = 1 / x;
        }

        while (m > 0) {
            if ((m & 1 )== 1) { //若m为奇数,m/2向下取整，此时会少1算一个底数，需要将其记录下来
                res *= x;       //x是底数
            }
            x *= x ;    //底数^2
            m >>= 1;    //右移一位（因为m>0，所以有符号和无符号结果都一样）
        }
        return res;
    }
}